{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Move Chips to The Same Position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCostToMoveChips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #玩筹码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有&nbsp;<code>n</code>&nbsp;个筹码。第 <code>i</code> 个筹码的位置是<meta charset=\"UTF-8\" />&nbsp;<code>position[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 <code>i</code> 个筹码的位置从&nbsp;<code>position[i]</code>&nbsp;改变为:</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>position[i] + 2</code>&nbsp;或&nbsp;<code>position[i] - 2</code>&nbsp;，此时&nbsp;<code>cost = 0</code></li>\n",
    "\t<li><code>position[i] + 1</code>&nbsp;或&nbsp;<code>position[i] - 1</code>&nbsp;，此时&nbsp;<code>cost = 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回将所有筹码移动到同一位置上所需要的 <em>最小代价</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/15/chips_e1.jpg\" style=\"height: 217px; width: 750px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>position = [1,2,3]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第一步:将位置3的筹码移动到位置1，成本为0。\n",
    "第二步:将位置2的筹码移动到位置1，成本= 1。\n",
    "总成本是1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/15/chip_e2.jpg\" style=\"height: 306px; width: 750px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>position = [2,2,2,3,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们可以把位置3的两个筹码移到位置2。每一步的成本为1。总成本= 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>position = [1,1000000000]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= position.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= position[i] &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-move-chips-to-the-same-position](https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-move-chips-to-the-same-position](https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[2,2,2,3,3]', '[1,1000000000]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        return min(odds := sum(p & 1 for p in position), len(position) - odds)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, chips: List[int]) -> int:\n",
    "        odd = sum(1 for i in chips if i % 2 == 1)\n",
    "        return min(odd,len(chips) - odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        j, o = 0, 0\n",
    "        for p in position:\n",
    "            if p % 2 == 0:\n",
    "                o += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return j if j < o else o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p % 2 for p in position)  # 根据模 2 后的余数来统计奇偶个数\n",
    "        return min(cnt[0], cnt[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p%2 for p in position)\n",
    "        return min(cnt[0], cnt[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a,b = 0,0\n",
    "        for i in position:\n",
    "            if i % 2 == 0:\n",
    "                a += 1\n",
    "            else:\n",
    "                b += 1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        t = [0,0]\n",
    "        for v in position:\n",
    "            t[v%2]+=1\n",
    "        return min(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        judge = [0,0]\n",
    "        for i in range(0,len(position)):\n",
    "            if position[i]/2 == position[i]//2:\n",
    "                judge[1]+=1\n",
    "            else:\n",
    "                judge[0]+=1\n",
    "        return min(judge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        msum = 100\n",
    "        for i in position:\n",
    "            su = sum([(k-i)%2 for k in position])\n",
    "            if su < msum:\n",
    "                msum = su \n",
    "        return msum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        ret = sum(1 for num in position if num % 2 == 0)\n",
    "        return min(n - ret, ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        sum1 = sum2 = 0\n",
    "        for i in position:\n",
    "            if i%2 == 0:\n",
    "                sum1 += 1\n",
    "            else:\n",
    "                sum2 += 1\n",
    "        return min(sum1, sum2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        o_num = 0\n",
    "        j_num = 0\n",
    "        for item in position:\n",
    "            if item % 2 == 0:\n",
    "                o_num += 1\n",
    "            else:\n",
    "                j_num += 1\n",
    "        return min(o_num, j_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        return min(odds := sum(p & 1 for p in position), len(position) - odds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a,b = 0,0\n",
    "        for i in position:\n",
    "            if i % 2 == 0:\n",
    "                a += 1\n",
    "            else:\n",
    "                b += 1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        count_1, count_0 = 0, 0\n",
    "        for num in position:\n",
    "            if num%2==1:\n",
    "                count_1 += 1\n",
    "            else:\n",
    "                count_0 += 1\n",
    "        return min(count_0, count_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a=0\n",
    "        b=0\n",
    "        for i in position:\n",
    "            if i/2==i//2:\n",
    "                a+=1\n",
    "            else:\n",
    "                b+=1\n",
    "        if a<b:\n",
    "            return a\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a=Counter(i%2 for i in position)\n",
    "        return min(a[0],a[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        odd = sum(1 for x in position if x % 2 != 0)\n",
    "        return min(odd, len(position)-odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a=0\n",
    "        b=0\n",
    "        for i in position:\n",
    "            if i/2==i//2:\n",
    "                a+=1\n",
    "            else:\n",
    "                b+=1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        odd, even = 0, 0\n",
    "        for i in position:\n",
    "            if i%2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return min(odd, even)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        x = [0, 0]\n",
    "        for i in position:\n",
    "            if i % 2 == 0:\n",
    "                x[1] += 1\n",
    "            else:\n",
    "                x[0] += 1\n",
    "        return min(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        c1 = sum([1 for index, num in enumerate(position) if num % 2 == 1])\n",
    "        return min(c1, len(position)-c1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        coins=[0,0]\n",
    "        for p in position:\n",
    "            coins[p%2]+=1\n",
    "        return min(coins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        positions = Counter(position)\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for pos in positions:\n",
    "            if pos % 2 == 0:\n",
    "                even += positions[pos]\n",
    "            else:\n",
    "                odd += positions[pos]\n",
    "        return min(odd,even)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        oecnt = [0, 0]\n",
    "        \n",
    "        prev = -1\n",
    "        prevoe = None\n",
    "        \n",
    "        for x in position:\n",
    "            if x == prev:\n",
    "                oecnt[prevoe] += 1\n",
    "                continue\n",
    "                \n",
    "            prev = x\n",
    "            prevoe = x % 2\n",
    "            oecnt[prevoe] += 1\n",
    "            \n",
    "        return min(oecnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        x = collections.Counter([x%2 for x in position])\n",
    "        return min(x[0],x[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p % 2 for p in position)\n",
    "        return min(cnt[0], cnt[1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a=b=0\n",
    "        for i in range(len(position)):\n",
    "            if position[i]%2==0:\n",
    "                a=a+1\n",
    "            else:\n",
    "                b=b+1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        jishu = 0\n",
    "        oushu = 0\n",
    "        for c in position:\n",
    "            if c%2 == 0:\n",
    "                oushu +=1\n",
    "            else:\n",
    "                jishu +=1\n",
    "        return min(jishu,oushu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "#         a ,b = 0 , 0\n",
    "#         for i in range(len(position)):\n",
    "#             if position[i] % 2 == 0:\n",
    "#                 a += 1\n",
    "#             else: \n",
    "#                 b += 1\n",
    "#         return min(a ,b)\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        l = len(position)\n",
    "        a = sum(position[i] % 2 == 0 for i in range(l) )\n",
    "        return min(a ,l-a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n1, n2 = 0, 0\n",
    "        for v in position:\n",
    "            if v & 1:\n",
    "                n1 += 1\n",
    "            else:\n",
    "                n2 += 1\n",
    "        return min(n1, n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, nums: List[int]) -> int:\n",
    "        ou = 0\n",
    "        ji = 0\n",
    "        for num in nums:\n",
    "            if num % 2 == 0:\n",
    "                ou += 1\n",
    "            else:\n",
    "                ji += 1\n",
    "        return min(ou, ji)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt_0, cnt_1 = 0, 0\n",
    "        for i in position:\n",
    "            if i & 1:\n",
    "                cnt_1 += 1\n",
    "            else:\n",
    "                cnt_0 += 1\n",
    "        return min(cnt_0, cnt_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "\n",
    "        const = {'ou':0,'ji':0}\n",
    "\n",
    "        for num in position:\n",
    "            if num % 2 == 0:const['ou'] += 1\n",
    "            else:const['ji'] += 1\n",
    "\n",
    "        return const['ou'] if const['ou'] < const['ji'] else const['ji']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        ans1, ans2 = 0, 0\n",
    "        for x in position:\n",
    "            if x % 2 == 1:\n",
    "                ans1 += 1\n",
    "            else:\n",
    "                ans2 += 1\n",
    "        return min(ans1,ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        odd, even = 0, 0\n",
    "        for i in range(n):\n",
    "            if position[i]%2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return min(even, odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        a=0\n",
    "        b=0\n",
    "        for i in position:\n",
    "            if i%2==0:\n",
    "                a+=1\n",
    "            else:\n",
    "                b+=1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "图中题意为跳两步不消耗代价，也就是奇数位置到奇数位置、偶数位置到偶数位置不消耗代价，其他情况到相邻位置消耗1点代价。\n",
    "\n",
    "我们可以分别统计奇数位置和偶数位置筹码的总个数\n",
    "分别移动奇数筹码和偶数筹码到一对相邻的位置（奇数位置到奇数位置，偶数位置到偶数位置，不需要消耗代价）\n",
    "将总数少的位置的筹码全部移动到总数多的位置上即可（消耗总数少位置筹码的数量）\n",
    "\n",
    "作者：做个梦给你\n",
    "链接：https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "    '''\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        # 奇偶位置数量\n",
    "        m,n=0,0\n",
    "        for i in position:\n",
    "            if i %2==0:\n",
    "                m+=1\n",
    "            else:\n",
    "                n+=1\n",
    "        if m>n:\n",
    "            return n\n",
    "        else:\n",
    "            return m\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        arr={}\n",
    "        for i in position:\n",
    "            if i in arr.keys():\n",
    "                arr[i]+=1\n",
    "            else:\n",
    "                arr[i]=1\n",
    "                n,m=0,0\n",
    "        for key,value in arr.items():\n",
    "            if key % 2 == 0:\n",
    "                m+=value\n",
    "            else:\n",
    "                n+=value\n",
    "        if n > m:\n",
    "            return m\n",
    "        else:\n",
    "            return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        num_ou = 0\n",
    "        num_ji = 0\n",
    "        for num in position:\n",
    "            if num % 2 == 0:\n",
    "                num_ou += 1\n",
    "            else:\n",
    "                num_ji += 1\n",
    "        return num_ji if num_ou > num_ji else num_ou"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        ji = 0\n",
    "        ou = 0\n",
    "        for i in position:\n",
    "            if i % 2 == 1:\n",
    "                ji += 1\n",
    "            else:\n",
    "                ou += 1\n",
    "        \n",
    "        return min(ou, ji)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        result = [0]*(2)\n",
    "        \n",
    "        for j in range(0,len(position)):\n",
    "            if ((position[j]-1)%2) == 0:\n",
    "                result[0] = result[0] + 1\n",
    "            if ((position[j]-1)%2) == 1:\n",
    "                result[1] = result[1] + 1\n",
    "        return min(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        ans = sum((1 if x % 2 else 0) for x in position)\n",
    "        return ans if ans < len(position) - ans else len(position) - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        num_ou = 0\n",
    "        num_ji = 0\n",
    "        for num in position:\n",
    "            if num % 2 == 0:\n",
    "                num_ou += 1\n",
    "            else:\n",
    "                num_ji += 1\n",
    "        return min(num_ou,num_ji)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        ans1=0\n",
    "        ans2=0\n",
    "        ans=0\n",
    "        for i in position:\n",
    "            if i%2==0:\n",
    "                ans1=ans1+1\n",
    "            else:\n",
    "                ans2=ans2+1\n",
    "        if ans1>=ans2:\n",
    "            ans=ans2\n",
    "        else:\n",
    "            ans=ans1\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        odd = [ 1 for p in position if p%2!=0]\n",
    "        oddCount = len(odd)\n",
    "        evenCount = n-oddCount\n",
    "        return oddCount if oddCount<evenCount else evenCount\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p % 2 for p in position)  # 根据模 2 后的余数来统计奇偶个数\n",
    "        return min(cnt[0], cnt[1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        single = 0\n",
    "        for i in position:\n",
    "            if i%2:\n",
    "                single+=1\n",
    "        return min(single, len(position)-single)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        even = 0\n",
    "        odd = 0\n",
    "        for i in range(n):\n",
    "            location = position[i]\n",
    "            if location %2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return odd if odd<even else even\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p % 2 for p in position)  # 根据模 2 后的余数来统计奇偶个数\n",
    "        return min(cnt[0], cnt[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        odd=0\n",
    "        even=0\n",
    "        for p in position:\n",
    "            if p % 2==0:\n",
    "                even+=1\n",
    "            else:\n",
    "                odd+=1\n",
    "        return min(odd,even)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        odd = [ 1 for p in position if p%2!=0]\n",
    "        oddCount = len(odd)\n",
    "        evenCount = n-oddCount\n",
    "        return oddCount if oddCount<evenCount else evenCount\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = [0, 0]\n",
    "        for n in position:\n",
    "            cnt[n%2] += 1\n",
    "        return min(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        n1, n2 = 0, 0\n",
    "        for v in position:\n",
    "            if v % 2:\n",
    "                n1 += 1\n",
    "            else:\n",
    "                n2 += 1\n",
    "        return min(n1, n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        odd = even = 0\n",
    "        for pos in position:\n",
    "            if pos % 2 == 1:\n",
    "                odd += 1\n",
    "            else:\n",
    "                even += 1\n",
    "        return min(odd, even)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        odds = 0\n",
    "        n = len(position)\n",
    "        for p in position:\n",
    "            if not p & 1: odds += 1\n",
    "        return min(odds, n - odds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        l = [0, 0]\n",
    "        for i in position:\n",
    "            l[i & 1] += 1\n",
    "        return min(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        '''\n",
    "        res = 0\n",
    "        set1 = set(position)\n",
    "        maxcount = max(position.count(i) for i in set1)\n",
    "        for i in set1:\n",
    "            if position.count(i)==maxcount:\n",
    "                exp = i\n",
    "                break\n",
    "        for i in set1:\n",
    "            if i != exp:\n",
    "                res = res+abs(i-exp)%2*position.count(i)\n",
    "        return res\n",
    "        '''\n",
    "        ji = 0\n",
    "        ou = 0\n",
    "        for i in position:\n",
    "            if i%2 == 0:\n",
    "                ou = ou+1\n",
    "            else:\n",
    "                ji = ji+1\n",
    "        return min(ji,ou)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt=Counter(p%2 for p in position)\n",
    "        return min(cnt[0],cnt[1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p % 2 for p in position)  # 根据模 2 后的余数来统计奇偶个数\n",
    "        return min(cnt[0], cnt[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt=Counter(p%2 for p in position)\n",
    "        return min(cnt[0],cnt[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = collections.Counter(p % 2 for p in position)\n",
    "        return min(cnt[0], cnt[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Greedy. Time O(n) Space O(1)\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        odd, even = 0, 0\n",
    "        for pos in position:\n",
    "            if pos % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return min(odd, even)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        '''\n",
    "        res = 0\n",
    "        set1 = set(position)\n",
    "        maxcount = max(position.count(i) for i in set1)\n",
    "        for i in set1:\n",
    "            if position.count(i)==maxcount:\n",
    "                exp = i\n",
    "                break\n",
    "        for i in set1:\n",
    "            if i != exp:\n",
    "                res = res+abs(i-exp)%2*position.count(i)\n",
    "        return res\n",
    "        '''\n",
    "        ji = 0\n",
    "        ou = 0\n",
    "        for i in position:\n",
    "            if i%2 == 0:\n",
    "                ou = ou+1\n",
    "            else:\n",
    "                ji = ji+1\n",
    "        return min(ji,ou)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        p1=p2=0\n",
    "        for p in position:\n",
    "            if p % 2 == 0:\n",
    "                p2 += 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return min(p1,p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        ds = Counter(position)\n",
    "        n1,n2 = 0,0\n",
    "        for k in ds:\n",
    "            if k % 2:\n",
    "                n1 += ds[k]\n",
    "            else:\n",
    "                n2 += ds[k]\n",
    "        return min(n1,n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        num1, num2 = 0, 0\n",
    "        for i in position:\n",
    "            if i % 2 != 0:\n",
    "                num1 += 1\n",
    "            else:\n",
    "                num2 += 1\n",
    "        return min(num1, num2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        Res = float('INF')\n",
    "        for i in position:  # 暴力解法，遍历每一种情况\n",
    "            res = 0\n",
    "            for j in position:\n",
    "                res += 0 if abs(j-i)%2==0 else 1\n",
    "            \n",
    "            Res = min(Res, res)\n",
    "        return Res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        i=0\n",
    "        l1=0\n",
    "        l2=0\n",
    "        while  i<len(position):\n",
    "            if position[i]%2==0:\n",
    "                l1=l1+1\n",
    "            else:\n",
    "                l2=l2+1\n",
    "            i=i+1\n",
    "        return min(l1,l2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        cnt = Counter(p%2 for p in position)\n",
    "        return min(cnt[0],cnt[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        even = 0\n",
    "        odd = 0\n",
    "        for i in position:\n",
    "            if i & 1:\n",
    "                odd += 1\n",
    "            else:\n",
    "                even += 1\n",
    "        return min(odd,even)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        ji = 0\n",
    "        ou = 0\n",
    "        n = len(position)\n",
    "        for i in range(n):\n",
    "            if position[i] % 2==0:\n",
    "                ou+=1\n",
    "            else:\n",
    "                ji+=1\n",
    "        return min(ou,ji)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        r1=r2=0\n",
    "        d = defaultdict(int)\n",
    "        l = len(position)\n",
    "        for i in range(l):\n",
    "            d[position[i]]+=1\n",
    "        for k in d:\n",
    "            if k%2==0:\n",
    "                r2+=d[k]\n",
    "            else:\n",
    "                r1+=d[k]\n",
    "        return min(r1,r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostToMoveChips(self, position: List[int]) -> int:\n",
    "        even = odd = 0\n",
    "        for i in position:\n",
    "            if i % 2 == 0:\n",
    "                even += 1\n",
    "            else:\n",
    "                odd += 1\n",
    "        return min(even, odd)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
